class Solution(object):
    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        j = 0
        while j < len(nums):
            if nums[j] > n:
                break
            else:
                j += 1
        nums = nums[: j]
        m = len(nums)
        if not nums:
            index = 0
            count = 1
        else:
            if nums[0] == 1:
                index = 1
                count = 0
            else:
                index = 0
                count = 1
        prefix = 1
        while index < m:
            if nums[index] > prefix + 1:
                count += 1
                prefix = 2 * prefix + 1
            else:
                prefix += nums[index]
                index += 1
        while prefix < n:
            count += 1
            prefix = 2 * prefix + 1
        return count


data = Solution()
nums = [1, 2, 4]
n = 8
print(data.minPatches(nums, n))
nums = [1, 5, 10]
n = 20
print(data.minPatches(nums, n))
nums = [1, 7, 21, 31, 34, 37, 40, 43, 49, 87, 90, 92, 93, 98, 99]
n = 12
print(data.minPatches(nums, n))
